// AllShortestPaths.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#define MaxWeight 100

void AllShortestPaths(int **cost,int **Scost,int n)
{

	
	int i=0,j=0,k=0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			Scost[i][j] = cost[i][j];

	for(k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
			{
				if(Scost[i][j]>Scost[i][k]+Scost[k][j])
					Scost[i][j] = Scost[i][k]+Scost[k][j];
			}
}

int FindMaxWeight(int **cost,int n)
{
	int i = 0,j = 0;
	int MaxWeight_2=-10000;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(cost[i][j]>MaxWeight)
				cost[i][j] = MaxWeight;
	return MaxWeight;
}


int _tmain(int argc, _TCHAR* argv[])
{
	int n,i,j;
	FILE *fp;
	int **cost = NULL;
	int **Scost = NULL;
	


	if((fp=fopen("graph.txt","r"))==NULL)
	{	
		printf("FOPEN ERROR!");
		return -1;
	}

	fscanf(fp, "%d", &n);
	cost = (int **)malloc(n*sizeof(int*));
	for(i=0;i<n;i++)
		cost[i]=(int *)malloc(n*sizeof(int));
	Scost = (int **)malloc(n*sizeof(int*));
	for(i=0;i<n;i++)
		Scost[i]=(int *)malloc(n*sizeof(int));
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			fscanf(fp,"%d",&cost[i][j]);

	AllShortestPaths(cost,Scost,n);
	int UnReachableWeight = (n - 1) * FindMaxWeight(cost, n);

	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(i!=j)
			{
				if(Scost[i][j] > UnReachableWeight)
					printf("%d is unreachable to %d\n",i,j);
				else 
					printf("%d to %d COST is: %d\n",i,j,Scost[i][j]);
			}

	getchar();
	return 0;
}